/**
////给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中
//的字
////符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。 
////
//// 示例： 
////
//// 输入：
////big = "mississippi"
////smalls = ["is","ppi","hi","sis","i","ssippi"]
////输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]
//// 
////
//// 提示： 
////
//// 
//// 0 <= len(big) <= 1000 
//// 0 <= len(smalls[i]) <= 1000 
//// smalls的总字符数不会超过 100000。 
//// 你可以认为smalls中没有重复字符串。 
//// 所有出现的字符均为英文小写字母。 
//// 
//// Related Topics 字典树 数组 哈希表 字符串 字符串匹配 滑动窗口 👍 36 👎 0
//

*/

package com.xixi.dataStructure.tree.trieTree;

import java.util.ArrayList;
import java.util.List;

public class ID_InterView_17_17MultiSearchLcci {
public static void main(String[] args) {
Solution solution = new ID_InterView_17_17MultiSearchLcci().new Solution();

    int[][] result = solution.multiSearch("mississippi", new String[]{"is","ppi","hi","sis","i","ssippi"});

    for(int i = 0; i < result.length; ++i){
        for(int j = 0; j < result[i].length; ++j){
            System.out.print(result[i][j] + "\t");
        }
        System.out.println();
    }

}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] multiSearch(String big, String[] smalls) {

        if(big.length() == 0 || smalls.length == 0) return new int[smalls.length][big.length()];

        List<ArrayList<Integer>> resultArray = new ArrayList<ArrayList<Integer>>(smalls.length);

        //首先构建一个Trie树，把big拆开，每次前进一个位，写到Trie树中

        for(int bigIndex = 0; bigIndex < big.length(); ++bigIndex){
            TrieNode suffixTrie = new TrieNode('/');
            String suffixStr = big.substring(bigIndex);
            suffixTrie.insert(suffixStr);
            //循环遍历small中的每个char，
            for(int smallIndex = 0; smallIndex < smalls.length; ++smallIndex){
                if(resultArray.size() < smalls.length){
                    resultArray.add(new ArrayList<Integer>());
                }
                //看看是否是其中某个suffix的前缀
                if(suffixTrie.startsWith(smalls[smallIndex])){
                    //如果是的话，记录下small的位置对应的big的位置
                    ArrayList<Integer> smallMatch = resultArray.get(smallIndex);

                    smallMatch.add(bigIndex);
                }

            }



        }


        int[][] result = new int[smalls.length][];
        for(int i = 0;  i < smalls.length ; ++i){
            ArrayList<Integer> smallMatch = resultArray.get(i);
            if(smallMatch.isEmpty()){
                result[i] = new int[]{};
            }else{
                int [] smallMatchArray = new int[smallMatch.size()];
                for(int j = 0; j < smallMatch.size(); ++j){
                    smallMatchArray[j] = smallMatch.get(j);
                }

                result[i] = smallMatchArray;
            }

        }

        return result;

    }


    private class TrieNode {
        public char data;
        public TrieNode[] children = new TrieNode[26];
        public boolean isEndding = false;


        public TrieNode(){
        }

        public TrieNode(char data){
            this.data = data;
        }


        public void insert(String word) {
            TrieNode p = this;

            for(int i = 0; i < word.length() ;++i){
                int index = word.charAt(i) - 'a';//找到当前待字母的位置

                if(p.children[index] == null ){ //如果没插入过，就新建一个trie树对象
                    p.children[index] = new TrieNode(word.charAt(i));
                }
                p = p.children[index];
            }
            p.isEndding = true;//单词结尾，就修改结尾标记

        }

        public boolean search(String word) {
            TrieNode p = this;

            int i = 0;
            while(i < word.length()){ //依次查询每个字母
                int index = word.charAt(i) - 'a';//算出每个字母在数组中的位置
                p = p.children[index]; //找到当前待字母的位置
                if(p == null){ //如果没找到
                    return false;
                }else{//找到了,继续找下一个
                    ++i;
                }
            }//循环结束，p为最后一个字母了
            if(!p.isEndding){ //如果p不是最后一个字母
                return false;
            }

            return true;
        }

        public boolean startsWith(String prefix) {
            if(prefix.length() == 0) return false;
            TrieNode p = this;
            int i = 0;
            while(i < prefix.length()){ //依次查询每个字母
                int index = prefix.charAt(i) - 'a';//算出每个字母在数组中的位置
                p = p.children[index]; //找到当前待字母的位置
                if(p == null){ //如果没找到
                    return false;
                }else{//找到了,继续找下一个
                    ++i;
                }
            }//循环结束，p为最后一个字母了
            //就不用判断是否为endding了

            return true;
        }




    }


}
//leetcode submit region end(Prohibit modification and deletion)




}